package com.lmz.project.redis.arithmetic.sort;

/**
 * 随机算则排序
 */
public class RandomSelectSort {
    //找到数组种第K最大(最小)的值
    public static int first;
    public static int end;

    static int[] arr = {1, 5, 2, 4, 3};
    public static void main(String[] args) {
        int K =3; //求数组第1大的值
        System.out.println(randomizedSelect(arr,arr.length-K));
    }

    public static int randomizedSelect(int[] sums, int x) {
        int ans = -1;
        for (int l = 0, r = sums.length - 1; l <= r; ) {
            //将选中的位置定好
            partition(sums, l, r, sums[(l + (int) (Math.random() * (r - l + 1)))]);
            //查看当前的值是否在选中范围内
            if (first <= x && end >= x) {
                ans = sums[first];
                break;
            } else if (x < first) {
                r = first - 1;
            } else if (x > end) {
                l = end + 1;
            }
        }
        return ans;
    }


    public static void partition(int[] sums, int l, int r, int x) {
        first = l;
        end = r;
        int i = l;
        while (i <= end) {
            if (sums[i] == x) {
                i++;
            } else if (sums[i] < x) {
                swap(sums, i, first);
                first++;
                i++;
            } else {
                swap(sums, i, end);
                end--;
            }
        }
    }


    public static void swap(int[] sums, int a, int b) {
        int temp = sums[a];
        sums[a] = sums[b];
        sums[b] = temp;
    }



}
